home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / bipl.zip / PROGS.ZIP / RECGEN.ICN < prev    next >
Text File  |  1992-11-26  |  5KB  |  166 lines
  1. ############################################################################
  2. #
  3. #    File:     recgen.icn
  4. #
  5. #    Subject:  Program to generate context-free recognizer
  6. #
  7. #    Author:   Ralph E. Griswold
  8. #
  9. #    Date:     January 28, 1991
  10. #
  11. ###########################################################################
  12. #
  13. #     This program reads a context-free BNF grammar and produces an Icon
  14. #  program that is a recognizer for the corresponding language.
  15. #
  16. #     Nonterminal symbols are are enclosed in angular brackets. Vertical
  17. #  bars separate alternatives.  All other characters are considered to
  18. #  be terminal symbols.  The nonterminal symbol on the first line is
  19. #  taken to be the goal.
  20. #
  21. #     An example is:
  22. #
  23. #    <expression>::=<term>|<term>+<expression>
  24. #    <term>::=<element>|<element>*<term>
  25. #    <element>::=x|y|z|(<expression>)
  26. #
  27. #     Characters in nonterminal names are limited to letters and underscores.
  28. #  An underscore is appended for the recognizing procedure name to avoid
  29. #  possible collisions with Icon function names.
  30. #
  31. #     Lines beginning with an = are passed through unchanged. This allows
  32. #  Icon code to be placed in the recognizer.
  33. #
  34. ############################################################################
  35. #
  36. #  Limitations:
  37. #
  38. #     Left recursion in the grammar may cause the recognizer to loop.
  39. #  There is no check that all nonterminal symbols that are referenced
  40. #  are defined or for duplicate definitions.
  41. #
  42. ############################################################################
  43. #
  44. #  Reference:
  45. #
  46. #     The Icon Programming Language, Second Edition, Ralph E. and Madge T.
  47. #     Griswold, Prentice-Hall, 1990. pp. 180-187.
  48. #
  49. ############################################################################
  50. #
  51. #  See also:  pargen.icn
  52. #
  53. ############################################################################
  54.  
  55. global call            # name suffix and parens
  56. global goal            # nonterminal goal name
  57. global nchars            # characters allowed in a nonterminal name
  58.  
  59. procedure main()
  60.    local line            # a line of input
  61.  
  62.    call := "_()"
  63.    nchars := &letters ++ '_'
  64.  
  65.    while line := read() do {        # process lines of input
  66.       line ? {
  67.          case move(1) of {        # action depends on first character
  68.             "<":  tab(0) ? transprod()    # transform the production
  69.             "=":  write(tab(0))        # pass through
  70.             default: error()
  71.             }                # end case
  72.          }                # end scan
  73.       }                    # end while
  74.  
  75.    write("procedure main()")        # write out the main procedure
  76.    write("   while line := read() do {")
  77.    write("      writes(image(line))")
  78.    write("      if line ? (",goal,call," & pos(0)) then ")
  79.    write("         write(\": accepted\")")
  80.    write("      else write(\": rejected\")")
  81.    write("      }")
  82.    write("end")
  83.  
  84. end
  85.  
  86. #
  87. #  Transform a production.
  88. #
  89.  
  90. procedure transprod()
  91.    local sym                # the symbol being defined
  92.  
  93.    {
  94.                     # begin the procedure declaration
  95.       write("procedure ",sym := tab(many(nchars)),call) &
  96.       =">::="                # skip definition symbols
  97.       } | error()                # catch syntactic error
  98.    write("   suspend {")        # begin the suspend expression
  99.    transalts()                # transform the alternatives
  100.    write("      }")            # end the suspend expression
  101.    write("end")                # end the procedure declaration
  102.    write()                # space between declarations
  103.    /goal := sym                # first symbol is goal
  104.  
  105. end
  106.  
  107. #
  108. #  Transform a sequence of alternatives.
  109. #
  110. procedure transalts()
  111.    local alt                # an alternative
  112.  
  113.    writes("      ")            # write indentation
  114.    while alt := tab(upto('|') | 0) do {    # process alternatives
  115.       writes(" (")            # open parenthesis for alternative
  116.       alt ? transseq()            # transform the symbols
  117.       if move(1) then writes(") |")    # if there's more, close the parentheses
  118.                     # and add the alternation.
  119.       else {
  120.          write(")")            # no more, so just close the parentheses
  121.          break
  122.          }                # end else
  123.       }                    # end while
  124.  
  125. end
  126.  
  127. #
  128. #  Transform a sequence of symbols.
  129. #
  130. procedure transseq()
  131.  
  132.    repeat {
  133.       transsym()            # process a symbols
  134.       if not pos(0) then writes(",")    # if there's more, provide concatenation
  135.       else break            # else get out and return
  136.       }                    # end while
  137.  
  138. end
  139.  
  140. #
  141. #  Transform a symbol.
  142. #
  143. procedure transsym()
  144.  
  145.    if ="<" then {            # if it's a nonterminal
  146.       {                    # write it with suffix.
  147.          writes(tab(many(nchars)),call) &
  148.          =">"                # get rid of closing bracket
  149.          } | error()            # or catch the error
  150.       }                    # end then
  151.                     # otherwise transform nonterminal string
  152.    else writes("=",image(tab(upto('<') | 0)))
  153.  
  154.    return
  155.  
  156. end
  157.  
  158. #
  159. #  Issue error message and terminate execution.
  160. #
  161. procedure error()
  162.  
  163.    stop("*** malformed definition: ",tab(0))
  164.  
  165. end
  166.